package dp;

public class BestTimeToBuyAndSellStockSummary {

    public static class BestTimeToBuyAndSellStock121 {
        // 用minPrice记录当前元素之前的最小值, 一次通过; 不需要动态规划.
        public int maxProfit(int[] prices) {
            int minPrice = Integer.MAX_VALUE;
            int maxProfit = 0;
            for (int p : prices) {
                if (p > minPrice) {
                    maxProfit = Math.max(maxProfit, p - minPrice);
                } else {
                    minPrice = p;
                }
            }
            return maxProfit;
        }
    }

    public static class BestTimeToBuyAndSellStock122 {
        // 用minPrice记录当前元素之前的最小值, 一次通过; 不需要动态规划.
        public int maxProfit(int[] prices) {
            int minPrice = prices[0];
            int maxProfit = 0;
            for (int i = 1; i < prices.length; i++) {
                // 比较价格是否下滑, 有下滑立即在前一天卖出
                if (prices[i] <= prices[i-1]) {
                    if (minPrice < prices[i-1]) {
                        maxProfit += prices[i-1] - minPrice;
                    }
                    minPrice = prices[i];
                } else if (i == prices.length-1 && prices[i] > minPrice) {
                    // 注意最后一个要特殊处理
                    maxProfit += prices[i] - minPrice;
                }
            }
            return maxProfit;
        }

        // 动态规划解
        public int maxProfitByDP(int[] prices) {
            // 第i天后还持有股票
            int[] hold = new int[prices.length];

            // 第i天后不持有股票
            int[] clear = new int[prices.length];

            hold[0] = -prices[0];
            clear[0] = 0;

            for (int i = 1; i < prices.length; i++) {
                hold[i] = Math.max(
                        hold[i-1], // 继续持有
                        clear[i-1] - prices[i]); // 之前不持有, 现在买入
                clear[i] = Math.max(
                        hold[i-1] + prices[i], // 之前持有, 现在卖出
                        clear[i-1]); // 继续不持有
            }
            return Math.max(hold[prices.length-1], clear[prices.length-1]);
        }

        public int maxProfitByClimbing(int[] prices) {
            int maxProfit = 0;
            for (int i = 1; i < prices.length; i++) {
                if (prices[i] > prices[i-1]) {
                    maxProfit += prices[i] - prices[i-1];
                }
            }
            return maxProfit;
        }
    }
}
